package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：最小路径和</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/minimum-path-sum/
 * </pre>
 * <p>创建日期：2019年11月24日下午22:00:30</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code64MinimumPathSum</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code64MinimumPathSum
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
		 * 
		 * 说明：每次只能向下或者向右移动一步。
		 * 
		 * 示例:
		 * 
		 * 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
		 * 
		 */
		int minPathSum = minPathSum(new int[][] { {} });
		System.out.println(minPathSum);
	}

	/**
	 * 本题采用动态规划思路: 
	 * 		数组：grid[m][n]
	 * 		记dp[i][j]表示到达坐标(i,j)的最小路径和
	 * 		则有：
	 * 			dp[i][j] = min(dp[i][j-1],dp[i-1][j])+gird[i][j]
	 * 		考虑各种情况：
	 * 			dp[i][j]:{
	 * 						0,	数组为空/数组长度为0
	 * 						grid[0][0],	m=1 and n=1
	 * 						grid[i][j] + dp[i][j - 1]或grid[i][j] + dp[i - 1][j],	即一条路走到黑,m=1 or n=1
	 * 						min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
	 * 					}
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n^2)
	 * 
	 * @param grid
	 * @return
	 */
	public static int minPathSum(int[][] grid)
	{
		if (grid == null || grid.length <= 0)
		{
			return 0;
		}
		int[][] dp = new int[grid.length][grid[0].length];
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				if (i == 0 && j == 0)
				{
					dp[0][0] = grid[0][0];
					continue;
				}
				if (i == 0)
				{
					dp[i][j] = grid[i][j] + dp[i][j - 1];
					continue;
				}
				if (j == 0)
				{
					dp[i][j] = grid[i][j] + dp[i - 1][j];
					continue;
				}
				dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
			}
		}
		/**
		 * 循环打印dp结果集 [1,3,1], [1,5,1], [4,2,1]
		 */
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println();
		}
		return dp[grid.length - 1][grid[0].length - 1];
	}
}
